package com.yulan.BitOpt;

import org.junit.Test;

/**
 * 338. 比特位计数
 * 定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 */
public class LeetCode_338 {
    /**
     * 每个数都算一次
     */
    public int[] countBits(int num) {
        int[] ans = new int[num+1];
        for(int i = 0;i<=num;i++){
            ans[i] = countBitOne(i);
        }
        return  ans;
    }

    public int countBitOne(int n){
        int count = 0;
        while(n!=0){
            count += (n&0x1) == 1 ? 1 : 0;
            n >>= 1;
        }
        return count;
    }

    /**
     * Dp，每个数都是由前面的结果生成
     */
    public int[] dp1_countBits(int num) {
        int[] ans = new int[num+1];
        int i = 0, b = 1;
        while(b<=num){
            //
            while(i<b && i+b <= num){
                ans[i+b] = ans[i] + 1;
                i++;
            }
            i = 0;
            b <<= 1;
        }
        return ans;
    }

    /**
     * Dp，找规律，Dp(x) = Dp(x/2) + x%2
     */
    public int[] dp2_countBits(int num) {
        int[] ans = new int[num+1];
        for(int i = 1;i<=num;i++){
            ans[i] = ans[i>>1] + (i&1);
        }
        return ans;
    }

    /**
     * Dp ,P(x)=P(x&(x−1))+1;
     */
    public int[] dp3_countBits(int num){
        int[] ans = new int[num+1];
        for(int i = 1 ;i<=num;i++){
            ans[i] = ans[(i & (i-1))] + 1;
        }
        return ans;
    }




    @Test
    public void test1(){
        int i = 0;
        while(i<=16){
            System.out.println(i&(i-1));
            i++;
        }

    }
}
